package tsb.trinhnx.main;

import java.util.Arrays;

/**
 * We separate into 2 parts: Signal and value (absolutely value)
 * @author TrinhNX
 */
public class BigNumber implements Comparable<BigNumber> {
	// For signal mask
	private enum SIGNAL {
		POSITIVE, NEGATIVE, ZERO;
	}

	// Constant value ZERO
	public static final BigNumber ZERO = new BigNumber();
	// Constant value ONE
	public static final BigNumber ONE = new BigNumber(1L);
	// Variable to keep flag signal
	private SIGNAL signal;
	// The char array to keep value
	private char[] value;

	// Create default is 0 :D
	public BigNumber() {
		signal = SIGNAL.ZERO;
		value = new char[] { '0' };
	}

	/**
	 * Keep this as a private constructor :3
	 * Create big number (copy of another)
	 * @param another
	 */
	private BigNumber(final BigNumber another) {
		this.signal = another.getSignal();
		this.value = another.getValue();
	}

	/**
	 * Create big number from this input
	 * @param input
	 */
	public BigNumber(final String s_input) {
		// 1. Validation
		// Null one
		if (s_input == null) {
			throw new NullPointerException("Null input");
		}
		// Remove head/tail space
		String trim = s_input.trim();
		final int length = trim.length();
		// Empty one
		if (length == 0) {
			throw new NumberFormatException("Empty input");
		}
		// Convert to char array
		char[] c_input = trim.toCharArray();
		// Temporarily store each character inside an char array 
		char[] temp = new char[length];
		for (int i = 0; i < length; i++) {
			if (i == 0) {
				// Check the first char
				if (c_input[0] == '+') {
					// Positive, ok
					this.signal = SIGNAL.POSITIVE;
					i = i + 1; // increase this index
					temp[0] = '0'; // fake this header to 0
				}
				if (c_input[0] == '-') {
					// Negative, ok
					this.signal = SIGNAL.NEGATIVE;
					i = i + 1; // increase this index
					temp[0] = '0'; // fake this header to 0
				}
			}

			/**
			 * If flag = true, then this character is ok, copy it
			 * Else raise error
			 */
			if (Character.isDigit(c_input[i])) {
				// If valid, copy it
				temp[i] = c_input[i];
			} else {
				throw new NumberFormatException("Invalid character: " + c_input[i]);
			}
		}
		// Ok, now we have to normalize the temp (may 0000000)
		int temp_length = temp.length;
		int ignore_position = temp_length;
		for (int i = 0; i < temp_length; i++) {
			if (temp[i] != '0') {
				ignore_position = i;
				break;
			}
		}
		// Ok, copy the temp value to our value
		this.value = Arrays.copyOfRange(temp, ignore_position, temp_length);
		// OMG, our string is 000000000000, ok
		if (this.value.length == 0) {
			this.signal = SIGNAL.ZERO; // change to zero
			this.value = new char[] { '0' };
		}
		// If the signal is not set , hmm, ok, the input is 12312323
		if (this.signal == null) {
			this.signal = SIGNAL.POSITIVE;
		}
	}

	/**
	 * Create big number from this input
	 * @param input
	 */
	public BigNumber(final long l_input) {
		// Call the string constructor
		this(String.valueOf(l_input));
	}

	public SIGNAL getSignal() {
		return signal;
	}

	public char[] getValue() {
		return value;
	}

	public int getLength() {
		return this.value.length;
	}

	/**
	 * Compare this with another
	 * We have some cases
	 * POSITIVE > ZERO > NEGATIVE and reserve
	 *  Return 1 if this is bigger
	 *  Return 0 if equal
	 *  Return -1 if less than
	 */
	@Override
	public int compareTo(BigNumber another) {
		// NOTE: We don't worry about 000000000, they have been pre-rocessing
		// All constructor using the (string)
		int padding = this.value.length - another.getLength();

		// We padding the zeros to make they have the same length
		BigNumber firstNumber, secondNumber;
		if (padding >= 0) {
			firstNumber = this;
			// Clone only
			secondNumber = another.clone();
			secondNumber.paddingZero(padding);
		} else {
			firstNumber = this.clone();
			firstNumber.paddingZero(-padding);
			secondNumber = another;
		}
		char[] first_number = firstNumber.getValue();
		char[] second_number = secondNumber.getValue();
		/**
		 * It is longer, it is bigger
		 */
		// Flag to compare value between this and another
		int flag_value = 0;
		// Same? compare each character :D
		for (int i = 0; i < second_number.length; i++) {
			// Convert to integer
			int temp1 = first_number[i] - '0';
			int temp2 = second_number[i] - '0';
			if (temp1 > temp2) {
				flag_value = 1;
				break;
			} else if (temp1 < temp2) {
				flag_value = -1;
				break;
			}
			// If the same, ok, 0
			flag_value = 0;
		}

		// Now we have the flag_value
		// At this point we will compare the annotation
		SIGNAL this_flag = this.getSignal();
		SIGNAL another_flag = another.getSignal();
		/**
		 * 1. If value is bigger
		 * 	- If flag is + -> 1
		 * 	- If flag is - -> -1
		 * 2. If equal
		 * 	- same value, then 0
		 *  - true / false: 1
		 *  - false / true: -1
		 * 3. If value is smaller
		 * 	- If another flag is +, smaller -1
		 * 	- Else +1
		 */
		// Final adjustment
		if (flag_value > 0) {
			switch (this_flag) {
			case POSITIVE:
				flag_value = 1;
				break;
			default:
				flag_value = -1;
				break;
			}

		} else if (flag_value == 0) {
			// Same length, same signal :D, true :D
			if (this_flag == another_flag) {
				flag_value = 0;
			} else if (this_flag == SIGNAL.POSITIVE) {
				flag_value = 1;
			} else if (this_flag == SIGNAL.NEGATIVE) {
				flag_value = -1;
			} else if (this_flag == SIGNAL.ZERO) {
				if (another_flag == SIGNAL.POSITIVE) {
					flag_value = -1;
				} else {
					flag_value = 1;
				}
			} else {
				// This will never ever go here.
				System.err.println("Miss some case???" + this + "\tAnother: " + another);
			}

		} else {
			switch (another_flag) {
			case POSITIVE:
				flag_value = -1;
				break;
			default:
				flag_value = 1;
				break;
			}
		}

		return flag_value;
	}

	/**
	 * Clone this object :v :v :v
	 * Full of trick :P
	 * FIXME: Findbugs, it is better to implement copy constructor instead of clone :(
	 * In fact, we used the copy constructor inside here ;)
	 */
	public BigNumber clone() {
		BigNumber clone = new BigNumber(this);
		return clone;
	}

	/**
	 * Add another big number to this number
	 * @param another
	 * @return the new big number that from sum of this tow
	 * There are 4 cases
	 * 	A(positive) + B (positive) => ok 
	 * 	A(positive) + B (negative) = call subtract
	 * 	A(negative) + B (positive) = call subtract
	 * 	A(negative) + B(negative) => OK
	 * 	A(ZERO) return B
	 */
	public BigNumber addBigNumber(final BigNumber another) {
		BigNumber result = null;
		int this_compare = this.compareTo(ZERO);
		int another_compare = another.compareTo(ZERO);
		// If one of each is zero :v return the other
		result = this_compare == 0 ? another : (another_compare == 0 ? this : result);
		if (result != null) // Ok, we catche'm, no need to process more
			return result;
		// None zero length :v ok
		// From now, we will process with its clone.
		BigNumber firstNumber, secondNumber;
		// The flag to indicate the SIGNAL of result
		boolean flag_add = false;
		firstNumber = this.clone();
		secondNumber = another.clone();
		if (this_compare > 0) {
			if (another_compare < 0) {
				// this - another
				secondNumber.reserve(); // reserve its signal
				return firstNumber.subtractBigNumber(secondNumber);
			} else {
				// this + that
				flag_add = true;
			}
		} else {
			if (another_compare < 0) {
				// -this + -that
				flag_add = false;
			} else {
				// -this + that
				firstNumber.reserve(); // reserve this signal 
				return secondNumber.subtractBigNumber(firstNumber);
			}
		}
		// Ok processing A + B or -(A + B)
		int padding = firstNumber.getLength() - secondNumber.getLength();
		/**
		 *	1. Padding
		 *	2. Adding
		 */
		if (padding >= 0) {
			secondNumber.paddingZero(padding);
		} else {
			firstNumber.paddingZero(-padding);
		}

		// Ok, same length
		char[] first_number = firstNumber.getValue();
		char[] second_number = secondNumber.getValue();
		StringBuilder sb = new StringBuilder(1);
		int divisior = 0;
		for (int i = first_number.length - 1; i >= 0; i--) {
			// Convert to integer
			int temp1 = first_number[i] - '0';
			int temp2 = second_number[i] - '0';
			int value = (divisior + temp1 + temp2) % 10;
			// add to string builder
			sb.append(value);
			divisior = (divisior + temp1 + temp2) / 10;
		}
		// If remain divisior (9 + 1 = 1 0)
		if (divisior != 0) {
			sb.append(divisior);
		}
		// If this is sum of 2 negative :D
		if (!flag_add) {
			sb.append('-');
		}
		// Then reverse all ourstring and create new one ;)
		return new BigNumber(sb.reverse().toString());
	}

	/**
	 * Subtract this number with another number
	 * @param another
	 * @return
	 */
	public BigNumber subtractBigNumber(BigNumber another) {
		BigNumber firstNumber, secondNumber; // result and two clones :D
		firstNumber = this.clone();
		secondNumber = another.clone();
		int this_compare = firstNumber.compareTo(ZERO);
		int another_compare = secondNumber.compareTo(ZERO);
		// ok
		// 0 - A = -A (reserve)
		if (this_compare == 0) {
			secondNumber.reserve();
			return secondNumber;
		}
		// A - 0 = A
		if (another_compare == 0) {
			return firstNumber;
		}
		// Then no one is zero, ok.
		if (this_compare > 0) {
			// Case A - -B = A + B
			if (another_compare < 0) {
				secondNumber.reserve();
				return firstNumber.addBigNumber(secondNumber);
			} else {
				//  Case A - B 
				System.out.println("Case A - B");
			}
		} else {
			// Case - A - B = -A + -B 
			if (another_compare > 0) {
				secondNumber.reserve();
				return firstNumber.addBigNumber(secondNumber);
			} else {
				// Case B - A
				System.out.println("Case B - A");
			}
		}

		// Go here, so they have the same signal ex: 3(-) 5 (-)
		// Number to padding
		int padding;
		// The flag indicates the subtract result
		boolean flag_subtract = false;
		// Compare two of you
		int compare = firstNumber.compareTo(secondNumber);
		if (compare > 0) {
			// wow, this one is bigger than another
			// 6 > 3 or -3 > -6
			flag_subtract = true;
		} else if (compare == 0) {
			// Same, subtract = 0
			return ZERO;
		} else {
			// omg , -6 < -3 or 3 < 6 :(
			flag_subtract = false;
		}
		// Well then.
		// Now we force them have the same signal (+) to compare
		if (this_compare < 0 && another_compare < 0) {
			firstNumber.reserve(); // reserve
			secondNumber.reserve(); // reserve
		}
		// compare again and
		// set the padding for the smaller
		padding = firstNumber.getLength() - secondNumber.getLength();
		if (firstNumber.compareTo(secondNumber) >= 0) {
			secondNumber.paddingZero(padding);
		} else {
			firstNumber.paddingZero(-padding);
			// Swap them :3
			BigNumber temp = secondNumber;
			secondNumber = firstNumber;
			firstNumber = temp;
		}
		// At this point, we have to get the bigger value is first
		// Ok, same length
		char[] first_number = firstNumber.getValue();
		char[] second_number = secondNumber.getValue();

		StringBuilder sb = new StringBuilder(1);
		int carry = 0;
		for (int i = first_number.length - 1; i >= 0; i--) {
			// Convert to integer
			int temp1 = first_number[i] - '0';
			int temp2 = second_number[i] - '0';
			int value;
			if (temp1 < (temp2 + carry)) {
				value = (10 + temp1 - temp2 - carry) % 10;
				carry = 1;
			} else {
				value = (temp1 - temp2 - carry) % 10;
				carry = 0;
			}
			// add to stringbuilder
			sb.append(value);
		}
		//System.out.println("Subtract: " + sb.toString());
		if (!flag_subtract) {
			sb.append('-');
		}
		return new BigNumber(sb.reverse().toString());
	}

	/**
	 * Multiple this number with another number
	 * @param another
	 * @return
	 */
	public BigNumber multipleBigNumber(BigNumber another) {
		// wow, A x 0 = 0
		if (this.compareTo(ZERO) == 0 || another.compareTo(ZERO) == 0)
			return ZERO;

		StringBuilder sb = new StringBuilder(1);
		if (this.getSignal() != another.getSignal()) {
			sb.append('-');
		}
		// Clone, and to multiple with absolute value only
		BigNumber firstNumber, secondNumber;
		firstNumber = this.clone();
		firstNumber.absolute();
		secondNumber = another.clone();
		secondNumber.absolute();
		sb.append(multiple(firstNumber, secondNumber).toString());
		return new BigNumber(sb.toString());
	}

	/**
	 * Divide this number to another number
	 * IMplement: long division
	 * http://en.wikipedia.org/wiki/Long_division
	 * @param another
	 * @return
	 */
	public BigNumber[] divideBigNumber(BigNumber another) {
		// If divide to 0, error
		if (another.getSignal() == SIGNAL.ZERO) {
			throw new ArithmeticException("Divide to ZERO");
		}
		// Check the SIGNAL
		if (this.getSignal() != SIGNAL.POSITIVE || another.getSignal() != SIGNAL.POSITIVE) {
			throw new ArithmeticException("Currently just support positive division! Sorry");
		} else {
			// Ok, call our function
			return divide(this, another);
		}
	}

	/**
	 * Cast this to long value, here.
	 * when it can not cast back (bigger than max long)
	 * write the log
	 * @return
	 */
	public long toLong() {
		try {
			return Long.valueOf(this.toString());
		} catch (NumberFormatException e) {
			System.err.println("Long out of bound " + this);
		}
		return Long.MAX_VALUE;
	}

	@Override
	public String toString() {
		// Printout this :D
		StringBuilder sb = new StringBuilder(1);
		if (this.signal == SIGNAL.NEGATIVE) {
			sb.append('-');
		}
		for (int i = 0; i < this.value.length; i++) {
			sb.append(this.value[i]);
		}
		return sb.toString();
	}

	/**
	 * Divide 2 big number
	 * @param dividend
	 * @param divisor
	 * @return
	 * NOTE: Just support the positive division only
	 */
	private BigNumber[] divide(final BigNumber dividend, final BigNumber divisor) {
		BigNumber[] result = new BigNumber[2];
		// Save the first result
		result[0] = ZERO;
		result[1] = dividend;
		// Get the length
		int dividend_length = dividend.getLength();
		int divisor_length = divisor.getLength();
		// This divident is smaller, no need to process more
		if (dividend_length < divisor_length) {
			return result;
		} else {
			// Create string builder contains the result each time
			StringBuilder sb = new StringBuilder(1);
			// Create the new dividend number
			BigNumber dividend1 = dividend.powerMultiple(divisor_length - dividend_length);
			// Assign the first division value
			result = simpleDivide(dividend1, divisor);

			for (int i = divisor_length; i < dividend_length; i++) {
				String s = result[1].toString() + String.valueOf(dividend.getValue()[i] - '0');
				sb.append(result[0].toString());
				dividend1 = new BigNumber(s);
				// Re-division
				result = simpleDivide(dividend1, divisor);
			}
			sb.append(result[0].toString());
			// The remain is ok, 
			// Create the result base on string
			result[0] = new BigNumber(sb.toString());
			return result;
		}
	}

	/**
	 * Private function, it is a general function than the multipleBigNumber :D
	 * @param x
	 * @param y
	 * @return
	 */
	private BigNumber multiple(final BigNumber x, final BigNumber y) {
		// Clone them :3
		BigNumber firstNumber = x.clone();
		BigNumber secondNumber = y.clone();
		int first_length = firstNumber.getLength();
		int second_length = secondNumber.getLength();
		// Get the max value length
		// Simple case
		if (first_length == 1 || second_length == 1) {
			return firstNumber.simpleMultiple(secondNumber);
		}
		int max_length = first_length > second_length ? first_length : second_length;
		// Decide how many padding number
		int padding_length = makePaddingEqual(max_length);
		firstNumber.paddingZero(padding_length - x.getLength());
		secondNumber.paddingZero(padding_length - y.getLength());
		// Complete padding
		// Separate X = x1 * 10^n/2 +  x2
		BigNumber high1, low1, high2, low2;
		high1 = firstNumber.powerMultiple(-padding_length / 2);
		low1 = firstNumber.moduleMultiple(padding_length / 2);
		high2 = secondNumber.powerMultiple(-padding_length / 2);
		low2 = secondNumber.moduleMultiple(padding_length / 2);
		// http://en.wikipedia.org/wiki/Karatsuba_algorithm#Algorithm
		BigNumber U = multiple(low1, low2);
		BigNumber V = multiple(high1.addBigNumber(low1), high2.addBigNumber(low2));
		BigNumber W = multiple(high1, high2);
//		System.out.println("U: " + U + "\tV: " + V + "\tW: " + W);

		BigNumber Z0 = W.powerMultiple(padding_length);
		BigNumber Z1 = V.subtractBigNumber(W).subtractBigNumber(U);
		BigNumber Z2 = Z1.powerMultiple(padding_length / 2);

//		System.out.println("Z0: " + Z0 + "\tZ1: " + Z1 + "\tZ2: " + Z2);
		return Z0.addBigNumber(Z2).addBigNumber(U);
	}

	// For padding
	/**
	 * The number 2^k that 2^k-1 < length < 2^k
	 * Return the least bigger power of 2
	 * ex: 12 => return 16
	 * 	8 = > return 8 
	 * @param length
	 * @return
	 * 
	 */
	private int makePaddingEqual(final int length) {
		int temp = 1;
		while (temp < length) {
			temp = temp * 2;
		}
		return temp;
	}

	// TrinhNX 12/25:
	// TO support multiple, we use karatsuba algorithm
	// Ok, we predefine 2 functions
	// 1. Multiple with Power of 10 (10,100 10000 1000000)
	// 2. Simple multiple with one value
	/**
	 * This looks the same shift operator
	 * NOTE: we use the base 10 :D
	 * If degree is bigger than 0, than appending 0 to the right
	 * If degree is smaller than 0, than shift from right to left.
	 * @param degree
	 * @return
	 * 	If this is 0, return zero
	 * 	If degree = 0, return itself
	 * 
	 */
	private BigNumber powerMultiple(final int degree) {
		// If zero x or degree = 0 -> return itselft
		if (degree == 0) {
			return this.clone();
		}

		if (this.compareTo(ZERO) == 0) {
			return ZERO;
		}

		StringBuilder sb = new StringBuilder(1);
		// Ok, we just simply append 0000 after these values :3
		// Make sure we keep the same signal
		if (this.getSignal() == SIGNAL.NEGATIVE) {
			sb.append('-');
		}
		// Ok, if degree is -, that will separate it
		// ex: 1234567 .power -3 => move 3 from right => 1234
		if (degree < 0) {
			// Note, we limited this to length only
			// that mean , not accept 123. power -3
			if (-degree >= this.getLength()) {
				throw new IndexOutOfBoundsException("Stop it, do not accept: " + degree);
			}
			// Note that degree is negative :3
			for (int i = 0; i < this.getLength() + degree; i++) {
				sb.append(this.value[i]);
			}
		} else {
			// Ok, it is positive, add zero :3
			sb.append(this.getValue());
			for (int i = 0; i < degree; i++) {
				sb.append('0');
			}
		}
		return new BigNumber(sb.toString());
	}

	/**
	 * The module of % base 10^degree
	 * @param degree
	 * @return
	 * If the degree is 0 or bigger than its length, return itselft 
	 * vd: 12 % 100 = 12
	 * If 
	 */
	private BigNumber moduleMultiple(final int degree) {
		// If zero x or degree = 0 -> return itselft
		if (degree == 0 || degree >= this.getLength()) {
			return this.clone();
		}
		if (this.compareTo(ZERO) == 0) {
			return ZERO;
		}

		StringBuilder sb = new StringBuilder(1);
		for (int i = (this.getLength() - degree); i < this.getLength(); i++) {
			sb.append(this.value[i]);
		}
		return new BigNumber(sb.toString());
	}

	/**
	 * Simple multiple this with 0 1 2 3 4 5 6 7 8 9
	 * @param another
	 * @return
	 */
	private BigNumber simpleMultiple(BigNumber another) {
		// Here big Number x small  = small x BigNUmber
		// but our implementation, it is better to 
		// Loop over the small and do addition :D
		BigNumber result = ZERO; // Define zero
		BigNumber firstNumber, secondNumber;
		firstNumber = this.clone();
		secondNumber = another.clone();
		if (this.getSignal() == SIGNAL.ZERO || another.getSignal() == SIGNAL.ZERO)
			return ZERO;
		// Wow, this is the small
		if (firstNumber.getLength() == 1) {
			// Type cast back to int
			int this_value = (int) (firstNumber.toLong());
			for (int i = 0; i < this_value; i++) {
				result = result.addBigNumber(secondNumber);
			}

		} else if (secondNumber.getLength() == 1) {
			// Type cast back to int
			int another_value = (int) (secondNumber.toLong());
			for (int i = 0; i < another_value; i++) {
				result = result.addBigNumber(firstNumber);
			}
		} else {
			System.err.println("troll me?");
			throw new NumberFormatException("Fuck you");
		}
		return result;
	}

	/**
	 * Simple division (from 0 -> 9) only
	 * @param dividend
	 * @param divisor
	 * @return
	 * return 1st element is the the result
	 * 		2nd element is the remain
	 * vd: 12/ 16 = [0, 16]
	 * 12 /2 = [6, 0]
	 * NOTE:
	 */
	private BigNumber[] simpleDivide(final BigNumber dividend, final BigNumber divisor) {
		BigNumber[] result = new BigNumber[2];
		// Luu tru thuong va so du
		BigNumber firstNumber = ZERO;
		BigNumber secondNumber = dividend;

		int counter = 0;
		while (secondNumber.compareTo(divisor) >= 0) {
			counter = counter + 1;
			firstNumber = new BigNumber(counter);
			secondNumber = secondNumber.subtractBigNumber(divisor);
		}
		if (counter > 9) {
			System.err.println("WTF is goin'" + dividend + "\tDivisor" + divisor);
		}
		result[0] = firstNumber;
		result[1] = secondNumber;
		return result;
	}

	/**
	 * NOTE: I mark this private, the outside should not do anything with this functions
	 * @param padding
	 * @return
	 * eg: 2 -> padding 3 => 0002
	 */
	private void paddingZero(int padding) {
		if (padding < 0) {
			throw new NumberFormatException(" Not valid padding: " + padding);
		} else if (padding == 0) {
			// Nothing to do :D
		} else {
			StringBuilder sb;
			sb = new StringBuilder(1);
			for (int i = 0; i < padding; i++) {
				sb.append('0');
			}
			sb.append(this.value);
			this.value = sb.toString().toCharArray();
		}
	}

	/**
	 * Make this become reserve
	 * 1 -> -1
	 * -1 > 1
	 * 0 -> 0 :D
	 */
	private void reserve() {
		int compare = this.compareTo(ZERO);
		if (compare == 0) {
			// Do nothing :D keep this :D
		} else if (compare == 1) {
			// Oh oh, positive, ok, set negative
			this.signal = SIGNAL.NEGATIVE;
		} else {
			// ok set to positive
			this.signal = SIGNAL.POSITIVE;
		}
	}

	/**
	 * Return the absolute value of this
	 * ex: -12 =>12
	 */
	private void absolute() {
		switch (this.getSignal()) {
		case NEGATIVE:
			// If is negative, reverse it
			reserve();
			break;
		default:
			// The other, nothing to do
			break;
		}
	}
}
